package 回溯;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

//698 划分为k个相等的子集 （大量剪枝技巧）
public class Solution9 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % k != 0) return false;
        int target = sum / k;
        Arrays.sort(nums);
        dfs(nums.length - 1, new int[k], target, nums, k);
        //这里进行一个倒序的dfs，因为先将大数给放入桶中可以减少大量的递归和提前获取到是否存在
        return res;
    }
    boolean res = false;//记录最终结果和进行提前终止
    private void dfs(int idx, int[] bts, int target, int[] nums, int k) {
        if (idx == -1 || res) {
            res = true;
            return;
        }
        //如果这个值超过了平均值那就没必要继续了（无负数情况下）
        if(nums[idx] > target){
            return;
        }
        Set<Integer> usd = new HashSet();//这里的set的作用是用来记录桶中的当前和的值是否出现过
        //意思是将当前的桶的和的值存入到set中，如果这个桶装不下这个数，那其他的桶如果当前和的值和这个桶一样
        //那肯定也装不了这个值，直接遍历下一个桶
        for (int i = 0 ; i < k ; i++) {
            if (res) return;
            if (bts[i] + nums[idx] > target || usd.contains(bts[i])) continue;
            usd.add(bts[i]);//这句和下句的顺序不能颠倒，这里的意思是将当前桶中的和的值存入进行记录，而不是相加后的
            bts[i] += nums[idx];
            dfs(idx - 1, bts, target, nums, k);
            bts[i] -= nums[idx];
            //这里usd不需要移除，因为本身就是用来记录一种值的情况，然后剪枝的，这个记录不需要回溯
        }
    }
}
